HW#4 --- last modified February 07 2019 04:44:47..

Solution set.

Due date: May 8

Files to be submitted:
  Hw4.zip

Purpose: To gain experience with the Turing Machine model. To learn more about Turing and Karp reductions, completeness, and undecidability.

Related Course Outcomes:

LO9 -- Construct a Turing machine accepting some simple languages.

LO10 -- State in precise mathematical terms what is meant by undecidability of the Halting Problem, and be able to show the undecidability of simple extensions of the Halting Problem, using the reduction technique.

Specification:

Group 1 (Must be handwritten, due start of class Apr. 24).

1. Give an offline TM which when started with `x#y` on its read only input tape outputs `lfloor x/y rfloor` on its output tape. Assume `{0,1, #}` is the input alphabet and numbers are in binary (lead zeros not allowed). On bad inputs your TM should halt, with `#` on the tape. If `y` is `0` output `#`. If `x` is `0` and `y` is a nonzero integer the output should be `0`.
2. Given the offline TM above use the construction from class to give a diagram of a usual TM computing the same function.
3. Give the RAM that would result from applying the construction of class to the TM from Problem 2.
4. Give a nondeterministic Turing machine which recognizes the language of binary strings of integers `n` such that `n` is a product of integers `x` and `y` both of which are greater than `1`. You can give a high level description of your NTM.

Group 2 (Must be handwritten, due start of class May 1).

1. Explicitly write down a function `f:{0,1,2,3,4} -> P({0,1,2,3,4})` of your choice but not the identity function. Then write down the complement of the diagonal for your function.
2. Prove the Space Hierarchy theorem mentioned in class.
3. Define `\mbox{Sub-HALT}_{TM} = { langle M, w rangle | \mbox{M is a TM and there is a substring v of w on which M will halt}}`. Give a many-one reduction of `\mbox{HALT}_{TM}` to `\mbox{Sub-HALT}_{TM}`.
4. Show `\mbox(EQ)_(LBA) = { langle M, M' rangle | \mbox{M and M' are LBAs with the same language}}` is undecidable.

Group 3 (Must be handwritten, due start of class May 8).

1. Consider the machine `M` from this slide. Show the dominos that would be played using the PCP construction to simulate `M` on `\a\a\b\b\a`.
2. Let `L={langle M rangle | mbox(M is a TM that only accepts inputs of odd length)}`. Carefully use Rice's Theorem to show `L` is undecidable.
3. Reprove the last result without using Rice's Theorem.
4. Look up the `s_(mn)` theorem, and state what it is saying in your own words. Give an example of Currying in some language other than LISP or Scheme. Make sure your example is not easily Googleable.

For the coding portion of this assignment, I'd like you to experiment with writing a Quine variant. Quines are directly related to the Recursion theorem we'll be talking about in class. That said, by reading the Wikipedia article you can get started even before we reach that lecture. The program I'd like you to write is MultiQuine.java (put this in your submitted ZIP file). I will compile this program (assume Java 1.6) using the line:

javac MultiQuine.java

from the folder containing your homework. Then I will run it using:

java MultiQuine some_int

where some_int is a positive integer like 1,2,3, 4 or 5, etc. Your program is allowed to use this command line argument, and it is allowed to use System.out.print and System.out.println, but is otherwise not allowed to use I/O. Your program when run in this fashion should then output its own source code some_int many times. Writing a Quine variant does not mean you should shirk the Departmental Java Coding guidelines or be lazy on documentation. These will still be worth a point for this assignment. In addition, your code must contain non-trivial Javadoc comments (those of the form /** */). Non-trivial means the comments should use at least @param and @return. Your code should also have at least two methods. If the supplied command line argument to your program is not present or is not a positive integer, your program should go into "javadoc" mode. In this mode, your program should output a web page for just its Javadoc comments. To be more precise, the web page should validate as HTML 5 using the W3C Validator. A minimally acceptably formatted HTML 5 page might look like:

<!DOCTYPE html>
<html> 
<head> 
<title>Javadocs for MultiQuine.java</title>
<meta charset="utf-8" />
</head> 
<body> 
<h1>Class MultiQuine</h1>
whatever the Javadocs on the class said for MultiQuine
<h2>Field Summary</h2>
<p>This class has no field variables.</p>
<h2>Constructor Summary</h2>
<div class="constructor">
<p><b>MultiQuine()</b> dummy constructor does nothing (material after method name comes
from Javadoc comment)</p>
</div>

<h2>Method Summary</h2>
<div class="method">
<h3>MyMethod1(String arg1, int arg2)</h3>
<p>takes arg1 computes out</p>
<h4>Parameters</h4>
<p><b>arg1</b> whatever @param said I'm for</p>
<p><b>arg2</b> whatever @param said I'm for</p>
<h4>Returns</h4>
<p>whatever @return says</p>
</div>

<div class="method">
<h3>MyMethod2(float arg1)</h3> 
<p>takes arg1 computes out</p>
<h4>Parameters</h4>
<p><b>arg1</b> whatever @param said I'm for</p>
<h4>Returns</h4>
<p>whatever @return says</p>
</div>
</body>
</html>

Of course what your program should output should be based on your code's Javadocs. This completes the description of the coding portion of the assignment.

Point Breakdown